/**
 背包问题，没通过提交，待优化
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
export var coinChange = function (coins, amount) {
  if (amount === 0) return 0
  coins.sort((a, b) => a - b)
  const jStartIdx = coins[0]
  const jLen = amount - jStartIdx + 2
  const dp = new Array(coins.length + 1).fill(0).map(() => new Array(jLen).fill(0))
  for (let i = 0; i < coins.length; i++) {
    const n = coins[i]
    for (let j = jStartIdx; j <= amount; j++) {
      if (j === 0) {
        dp[i + 1][j] = 0
        continue
      }

      const cnt = Math.floor(j / n)
      if (!cnt) {
        // 当前面值大于目标值，不能使用当前面值
        dp[i + 1][j] = dp[i][j]
        continue
      }
      let remainder = j % n
      // 当j能被当前面值除尽时，说明只需cnt个当前面值的硬币即可
      if (remainder === 0) dp[i + 1][j] = cnt
      else {
        let k = cnt
        while (k > 0) {
          remainder = (cnt - k) * n + remainder
          const pre = dp[i][remainder]
          if (pre > 0) {
            dp[i + 1][j] = k + pre
            if (dp[i][j] > 0) dp[i + 1][j] = Math.min(dp[i][j], dp[i + 1][j])
            break
          }
          k--
        }
        if (k === 0) dp[i + 1][j] = dp[i][j]
      }
    }
  }
  // console.log(dp)
  return dp[coins.length][amount] || -1
}
